package org.everyday;

import java.util.ArrayList;
import java.util.List;

/**
 * @version v1.0.0
 * 创建时间：2022/7/14 10:00
 */
public class WordFilter {

    Trie prefixTree;
    Trie suffixTree;

    public WordFilter(String[] words) {
        prefixTree = new Trie();
        suffixTree = new Trie();
        for (int i = 0; i < words.length; i++) {
            prefixTree.insertNode(words[i], i);
            //翻转字符串
            String reverseStr = new StringBuilder(words[i]).reverse().toString();
            suffixTree.insertNode(reverseStr, i);
        }
    }

    public int f(String prefix, String suffix) {
        suffix = new StringBuilder(suffix).reverse().toString();

        List<Integer> prefixList;
        List<Integer> suffixList;

        //获取满足前缀的字符串列表
        prefixList = prefixTree.search(prefix);
        //获取满足后缀的字符串列表
        suffixList = suffixTree.search(suffix);
        int prefixLen = prefixList.size();
        int suffixLen = suffixList.size();
        if (prefixLen == 0 || suffixLen == 0) {
            return -1;
        }
        //寻找最大交集 list是单调递增的 从后向前匹配即可
        int i = prefixLen - 1;
        int j = suffixLen - 1;
        while (i >= 0 && j >= 0) {
            int prefixIndex = prefixList.get(i);
            int suffixIndex = suffixList.get(j);
            if (prefixIndex == suffixIndex) {
                return prefixIndex;
            } else if (prefixIndex > suffixIndex) {
                i--;
            } else {
                j--;
            }
        }
        return -1;
    }

    class TrieNode {
        List<Integer> indexList;//
        TrieNode[] child;
        public TrieNode() {
            indexList = new ArrayList<>();
            child = new TrieNode[26];
        }
    }

    class Trie {
        TrieNode root;
        public Trie(){
            root = new TrieNode();
        }

        public void insertNode(String word,int index){
            TrieNode cur = root;
//            cur.indexList.add(index);
            for(int i=0;i<word.length();i++){
                int charIndex = word.charAt(i)-'a';
                if(cur.child[charIndex]==null){
                    cur.child[charIndex] = new TrieNode();
                }
                cur = cur.child[charIndex];
                cur.indexList.add(index);
            }
        }

        public List<Integer> search(String word){
            TrieNode cur =root;
            for (int i=0;i<word.length();i++) {
                int index = word.charAt(i)-'a';
                if (cur.child[index]==null){
                    // find nothing
                    return new ArrayList<>();
                }
                cur = cur.child[index];
            }
            return cur.indexList;
        }
    }

    public static void main(String[] args) {
        WordFilter wordFilter = new WordFilter(new String[]{"apple","ae","ae","ae"});
        System.out.println(wordFilter.f("a", "e"));
    }
}